package sort;

import util.Util;

/**
 * createby heart on 2021/5/29
 */
public class QuickSort {


    public static void quickSort(int[] arr,int l,int r) {
        if (l < r) {
            //Util.swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
            int[] p = partition(arr, l, r);
            quickSort(arr,l,p[0]-1);
            quickSort(arr,p[1]+1,r);
        }
    }
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) return;
        quickSort(arr,0,arr.length-1);
    }

    public static int[] partition(int[] arr,int l,int r) {
        int less = l - 1;
        int more = r + 1;
        while (l < more) {
            if (arr[l] < arr[r]) {
                Util.swap(arr,l++,++less);
            } else if (arr[l] > arr[r]) {
                Util.swap(arr,l,--more);
            } else {
                l++;
            }
        }
        return new int[] {less+1,more};
    }

    public static void main(String[] args) {
        int[] arr=  {7,6,5,4,3,2,1};

        quickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }


}
